package collection;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

import org.junit.Test;

import cn.hutool.core.lang.Console;
import lombok.AllArgsConstructor;
import lombok.Data;

/**
 * @author jiangwz
 * @create 2019/9/9.
 */
public class CollectionTests {


    @Test
    public void defaultArrayListTest(){
        /**
         * 底层操作是 数组
         * this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
         * private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
         */
        ArrayList<Integer> lists = new ArrayList<>();

        /**
         * 如果不填容量,默认再添加的时候初始化为10
         * 扩容: 如果数组的大小无法容纳时,进行扩容, 也就是当插入第11条数据时,发现塞不下了,先扩容,再塞
         * 每次扩容为原来的1.5倍
         * grow方法里面的这一行,扩容1.5倍, 右移1位代表变小一半(
         * int newCapacity = oldCapacity + (oldCapacity >> 1);
         * )
         * 增删慢,查询快
         */
        lists.add(1);
        for (int i = 0; i < 20; i++) {
            lists.add(i);
        }
    }

    /**
     * 链表
     */
    @Test
    public void testLinkedList(){


        /**
         *     private static class Node<E> {
         *         E item;
         *         Node<E> next;
         *         Node<E> prev;
         *
         *         Node(Node<E> prev, E element, Node<E> next) {
         *             this.item = element;
         *             this.next = next;
         *             this.prev = prev;
         *         }
         *     }
         *     底层是链表,一个连着一个,增删快,查询慢
         */
        LinkedList<Integer> lists = new LinkedList<>();
        lists.add(1);
        lists.add(2);
    }

    @Test
    public void testHashMap2(){
        HashMap<Integer, Object> map = new HashMap<>();
//        map.put(1,1);
        map.get(1);
        System.out.println("0".hashCode());

        List<Integer> list = Arrays.asList(0, 16, 32, 48, 64, 80, 96, 112, 128, 144);
        for (Integer i : list) {
            map.put(i, i);
        }
    }

    /**
     * key = 分区
     * key=0,val=[Model{val=0, hash=0}, Model{val=16, hash=16}, Model{val=32, hash=32}, Model{val=48, hash=48}, Model{val=64, hash=64}, Model{val=80, hash=80}, Model{val=96, hash=96}]
     * key=1,val=[Model{val=1, hash=1}, Model{val=17, hash=17}, Model{val=33, hash=33}, Model{val=49, hash=49}, Model{val=65, hash=65}, Model{val=81, hash=81}, Model{val=97, hash=97}]
     * key=2,val=[Model{val=2, hash=2}, Model{val=18, hash=18}, Model{val=34, hash=34}, Model{val=50, hash=50}, Model{val=66, hash=66}, Model{val=82, hash=82}, Model{val=98, hash=98}]
     * key=3,val=[Model{val=3, hash=3}, Model{val=19, hash=19}, Model{val=35, hash=35}, Model{val=51, hash=51}, Model{val=67, hash=67}, Model{val=83, hash=83}, Model{val=99, hash=99}]
     * key=4,val=[Model{val=4, hash=4}, Model{val=20, hash=20}, Model{val=36, hash=36}, Model{val=52, hash=52}, Model{val=68, hash=68}, Model{val=84, hash=84}]
     * key=5,val=[Model{val=5, hash=5}, Model{val=21, hash=21}, Model{val=37, hash=37}, Model{val=53, hash=53}, Model{val=69, hash=69}, Model{val=85, hash=85}]
     * key=6,val=[Model{val=6, hash=6}, Model{val=22, hash=22}, Model{val=38, hash=38}, Model{val=54, hash=54}, Model{val=70, hash=70}, Model{val=86, hash=86}]
     * key=7,val=[Model{val=7, hash=7}, Model{val=23, hash=23}, Model{val=39, hash=39}, Model{val=55, hash=55}, Model{val=71, hash=71}, Model{val=87, hash=87}]
     * key=8,val=[Model{val=8, hash=8}, Model{val=24, hash=24}, Model{val=40, hash=40}, Model{val=56, hash=56}, Model{val=72, hash=72}, Model{val=88, hash=88}]
     * key=9,val=[Model{val=9, hash=9}, Model{val=25, hash=25}, Model{val=41, hash=41}, Model{val=57, hash=57}, Model{val=73, hash=73}, Model{val=89, hash=89}]
     * key=10,val=[Model{val=10, hash=10}, Model{val=26, hash=26}, Model{val=42, hash=42}, Model{val=58, hash=58}, Model{val=74, hash=74}, Model{val=90, hash=90}]
     * key=11,val=[Model{val=11, hash=11}, Model{val=27, hash=27}, Model{val=43, hash=43}, Model{val=59, hash=59}, Model{val=75, hash=75}, Model{val=91, hash=91}]
     * key=12,val=[Model{val=12, hash=12}, Model{val=28, hash=28}, Model{val=44, hash=44}, Model{val=60, hash=60}, Model{val=76, hash=76}, Model{val=92, hash=92}]
     * key=13,val=[Model{val=13, hash=13}, Model{val=29, hash=29}, Model{val=45, hash=45}, Model{val=61, hash=61}, Model{val=77, hash=77}, Model{val=93, hash=93}]
     * key=14,val=[Model{val=14, hash=14}, Model{val=30, hash=30}, Model{val=46, hash=46}, Model{val=62, hash=62}, Model{val=78, hash=78}, Model{val=94, hash=94}]
     * key=15,val=[Model{val=15, hash=15}, Model{val=31, hash=31}, Model{val=47, hash=47}, Model{val=63, hash=63}, Model{val=79, hash=79}, Model{val=95, hash=95}]
     */
    @Test
    public void testHash(){
        //{0=[0, 16, 32, 48, 64, 80, 96],
        // 1=[1, 17, 33, 49, 65, 81, 97],
        // 2=[2, 18, 34, 50, 66, 82, 98],
        // 3=[3, 19, 35, 51, 67, 83, 99], 4=[4, 20, 36, 52, 68, 84], 5=[5, 21, 37, 53, 69, 85], 6=[6, 22, 38, 54, 70, 86], 7=[7, 23, 39, 55, 71, 87], 8=[8, 24, 40, 56, 72, 88], 9=[9, 25, 41, 57, 73, 89], 10=[10, 26, 42, 58, 74, 90], 11=[11, 27, 43, 59, 75, 91], 12=[12, 28, 44, 60, 76, 92], 13=[13, 29, 45, 61, 77, 93], 14=[14, 30, 46, 62, 78, 94], 15=[15, 31, 47, 63, 79, 95]}
        Map<Integer, List<Model>> map = new ConcurrentHashMap<>();
        int tabSize = 16;
        for (int i = 0; i < 200; i++) {
            int hash = hash(i);
            int j = (tabSize - 1) & hash;
            List<Model> orDefault = map.getOrDefault(j, new ArrayList<>());
            orDefault.add(new Model(i, hash));
            map.put(j, orDefault);
        }

        map.forEach((key,val) -> {
            Console.log("key={},val={}", key, val);
        });
    }

    @Test
    public void resizeHighLow(){
        int oldCap = 15;
        List<Integer> list = Arrays.asList(0, 16, 32, 48, 64, 80, 96);
        for (Integer i : list) {
            int hashKey = hash(i);
            if ((hashKey & oldCap) == 0) {
                System.out.println("0="+ hashKey);
            }else {
                System.out.println("1="+ hashKey);
            }
        }


    }


    @Data
    @AllArgsConstructor
    class Model{
        // val
        private int val;
        // hash
        private int hash;

        @Override
        public String toString() {
            return "Model{" +
                    "val=" + val +
                    ", hash=" + hash +
                    '}';
        }
    }

    /**
     * 1.7 的 hash算法
     * @param key
     * @return
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

    /**
     * 1.8 的 hash算法
     * @param h key.hashCode()
     * @return
     */
    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

    /**
     * 解读HashMap1.8源码
     */
    @Test
    public void testHashMap(){

//        HashMap<String, Object> map = new HashMap<>();
//        for (int i = 0; i < 17; i++) {
//            map.put(""+i, i);
//        }

        // 如何模拟链表转红黑树
        /**
         * 思考,只要 hash值全部在同一个索引下即可
         * x & 15 = 0
         * 15 = 0000 1111
         * x  = 0000 0000
         * x  = 0001 0000
         * x  = 0010 0000
         * x  = 0100 0000
         * x  = 1000 0000
         * x  = 0011 0000
         * 1 << 4
         * 1*2 << 4
         * 1*2 + 1 << 4
         */
        HashMap<Integer, Object> map = new HashMap<>(10);
        // 因为树化要map里面要有64个元素,所以我提前加进去
        for (int i = 0; i < 60; i++) {
            map.put(i, i+60);
        }
        for (int i = 0; i < 200; i++) {
            int pow = (int) Math.pow(2, i);
            System.out.println(pow);
            int v = (int)pow << 4;
            map.put(v, i);
        }
    }


    @Data
    @AllArgsConstructor
    class App {
        private int id;
    }


    /**
     * 数组.链表.红黑树
     */
    @Test
    public void testConcurrentHashMap(){
        ConcurrentHashMap<Integer, Object> map = new ConcurrentHashMap<>();
        for (int i = 0; i < 200; i++) {
            map.put(i, i);
        }
        map.get(1);
    }

    /**
     * http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
     * LinkedHashMap 继承了HashMap
     */
    @Test
    public void testLinkedHashMap(){

        LinkedHashMap<Integer, Object> map = new LinkedHashMap();
        map.put(3,1);
        map.put(1,1);
        map.forEach((k,v) -> System.out.println(k+"-"+v));
    }

    @Test
    public void testHashSet(){
        HashSet<Integer> set = new HashSet<>();
        set.add(1);
    }

}
